package search;

public class MedianOfTwoSortedArrays {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int totalLength = nums1.length + nums2.length;

        int maxLength = Math.max(nums1.length, nums2.length);

        int p1 = 0;
        int p2 = 0;

        int value = 0;

        int leftIndex = (totalLength - 1) / 2;
        int rightIndex = leftIndex + 1;

        boolean isDouble = (totalLength & 1) == 0;

        int leftValue = 0;
        int rightValue = 0;

        for (int i = 0; i < maxLength; i++) {

            if (p1 >= nums1.length) {   //p1 遍历完了
                if (i == leftIndex) {
                    leftValue = nums2[p2];
                    if (!isDouble) {
                        return leftValue;
                    }
                } else if (i == rightIndex) {
                    rightValue = nums2[p2];
                    if (isDouble) {
                        return (leftValue + rightIndex)/2;
                    }
                    break;
                }
                p2++;
            } else if (p2 >= nums2.length) {   //p2 遍历完了
                if (i == leftIndex) {
                    leftValue = nums1[p1];
                    if (!isDouble) {
                        return leftValue;
                    }
                } else if (i == rightIndex) {
                    rightValue = nums1[p1];
                    if (isDouble) {
                        return (leftValue + rightIndex)/2;
                    }
                    break;
                }
                p1++;
            } else {
                value = nums1[p1] - nums2[p2];

                if (value >= 0) {
                    if (i == leftIndex) {
                        leftValue = nums2[p2];
                        if (!isDouble) {
                            return leftValue;
                        }
                    } else if (i == rightIndex) {
                        rightValue = nums2[p2];
                        if (isDouble) {
                            return (leftValue + rightIndex)/2;
                        }
                        break;
                    }
                    p2++;
                } else {
                    if (i == leftIndex) {
                        leftValue = nums1[p1];
                        if (!isDouble) {
                            return leftValue;
                        }
                    } else if (i == rightIndex) {
                        rightValue = nums1[p1];
                        if (isDouble) {
                            return (leftValue + rightIndex)/2;
                        }
                        break;
                    }
                    p1++;
                }
            }
        }

        return 0;
    }
}
